//==============================================================================
// Copyright (c) 2008-2013 Niall Ryan. All Rights Reserved.
//==============================================================================

#ifndef HYDRA_LAZYLOCKLIST_H
#define HYDRA_LAZYLOCKLIST_H 1

#include "hydra/allocators/DelayedFreeAllocator.h"
#include "hydra/locks/TTASLock.h"

namespace Hydra
{
	/**
	 * A list using lazy locking. The list is traversed without taking locks, when a modification needs
	 * to be made the nodes are locked and validated. If the validation fails the list must be re-traversed.
	 * Differs from the OptimisticLockList by marking nodes which are to be removed before they are physically
	 * removed from the list, this allows the nodes to be validated without re-traversing the entire list.
	 *
	 * The allocator's garbage collector is used to delete nodes, as we can still have Iterators to nodes after
	 * they have been removed from the list.
	 */
	template<typename T, typename Allocator=DelayedFreeAllocator, typename Lock=TTASLock>
	class LazyLockList
	{
	private:
		struct Node
		{
			Node() { m_isMarked = false; }
			T m_item;
			Lock m_lock;
			Atomic<Node*> m_next;
			Atomic<bool> m_isMarked;
		};

	public:
        static_assert(Allocator::kAllowsDanglingPointers, "Allocator must allow dangling pointers");

		/**
		 * The list is traversed without taking locks, so the iterator can be traversing nodes which have already
		 * been removed from the list. To make a modification to the list the Iterator must be locked and validated.
		 */
		class Iterator
		{
			friend class LazyLockList;
		public:
			Iterator(LazyLockList& list) : m_list(list)
			{
				m_pred = &list.m_head;
				m_curr = m_pred->m_next;
				m_isLocked = false;
				m_isValidated = false;
			}
			~Iterator()
			{
				assert(!m_isLocked);
			}
			/**
			 * Returns the item currently pointed to by the Iterator and steps the Iterator to the next item in the list.
			 * Note that the returned item is not necessarily still in the list, lockAndValidate must be called to verify
			 * that the item has not been previously removed.
			 */
			const T next()
			{
				//no need to lock with the hasNext method. If hasNext returns true, then there will still be a valid next
				// pointer here too, although it may not be the same pointer
				assert(hasNext());
				assert(!m_isLocked);
				T value = m_curr->m_item;
				m_pred = m_curr;
				m_curr = m_curr->m_next;
				return value;
			}
			///Returns the item currently pointed to by the Iterator, without stepping forward
			const T peekNext()
			{
				assert(hasNext());
				return m_curr->m_item;
			}
			///Returns false if the Iterator is at the end of the list
			bool hasNext() const
			{
				return (m_curr->m_next != NULL);
			}
			/**
			 * Locks the item and verifies that it is has not been previously removed from the list. Returns true if
			 * the item is validated as being still a member of the list. The item must be unlocked after this call
			 * regardless of whether the validation succeeded or failed.
			 */
			bool lockAndValidate()
			{
				assert(!m_isLocked);
				m_pred->m_lock.lock();
				m_curr->m_lock.lock();
				m_isLocked = true;

				//check that m_pred still points to m_curr and neither are marked
				m_isValidated = (m_pred->m_next == m_curr) && !m_pred->m_isMarked && !m_curr->m_isMarked;
				return m_isValidated;
			}
			/**
			 * Unlocks an item which was previously locked using lockAndValidate, this must be called whether or not
			 * the validation succeeded.
			 */
			void unlock()
			{
				assert(m_isLocked);
				m_isLocked = false;
				m_isValidated = false;
				m_pred->m_lock.unlock();
				m_curr->m_lock.unlock();
			}
			void toFront()
			{
				assert(!m_isLocked);
				m_pred = &m_list.m_head;
				m_curr = m_pred->m_next;
			}
			bool isValidated()		{ return m_isValidated; }
		private:
			LazyLockList& m_list;
			Node* m_pred;
			Node* m_curr;
			bool m_isLocked;
			bool m_isValidated;
		};

		LazyLockList()
		{
			m_head.m_next = &m_alloc.m_tail;
			m_alloc.m_tail.m_next = NULL;
		}

		~LazyLockList()
		{
			//no need to lock here, if more than one thread is calling the destructor we have bigger problems
			Node* node = m_head.m_next;
			Node* nextNode = node->m_next;
			while( nextNode )
			{
				freeNode(node);
				node = nextNode;
				nextNode = node->m_next;
			}
		}

		void pushFront(const T& item)
		{
			//only necessary to lock head, no need to lock the next node since we never read from it
			m_head.m_lock.lock();

			Node* newNode = allocNode();
			newNode->m_item = item;
			newNode->m_next = m_head.m_next;
			m_head.m_next = newNode;

			m_head.m_lock.unlock();
		}

		bool front(T& item)
		{
			//no need to lock
			Node* node = m_head.m_next;	//atomic read, node will be either tail or a regular node
			while( node->m_next )	//test if node is tail, doesn't matter if next pointer has changed since the previous line
			{
				if( !node->m_isMarked )	//skip marked nodes, they aren't in the list
				{
					item = node->m_item;
					return true;
				}
				node = node->m_next;
			}
			return false;
		}

		bool popFront(T& item)
		{
			while( true )
			{
				Iterator iter(*this);
				if( iter.lockAndValidate() )
				{
					if( iter.hasNext() )
					{
						item = iter.peekNext();
						removeAndUnlock(iter);
						return true;
					}
					else
					{
						iter.unlock();
						break;
					}
				}
				iter.unlock();
			}
			return false;
		}

		/**
		 * Inserts the new item before the item currently pointed to by the Iterator. The iterator must be
		 * locked and validated before calling this function. The Iterator will be pointing to the new item
		 * after this function.
		 */
		void insert(Iterator& iter, const T& item)
		{
			assert(iter.isValidated());
			Node* newNode = allocNode();
			newNode->m_item = item;
			newNode->m_next = iter.m_curr;
			iter.m_pred->m_next = newNode;
			iter.m_curr->m_lock.unlock();
			iter.m_curr = newNode;
			iter.m_curr->m_lock.lock();
		}

		/**
		 * Same as insert, but unlocks the iterator after insertion. This is more efficient than calling insert
		 * followed by unlock.
		 */
		void insertAndUnlock(Iterator& iter, const T& item)
		{
			assert(iter.isValidated());
			Node* newNode = allocNode();
			newNode->m_item = item;
			newNode->m_next = iter.m_curr;
			iter.m_pred->m_next = newNode;
			iter.unlock();
			iter.m_curr = newNode;
		}

		/**
		 * Tests if the specified item is contained in the list, uses operator== to compare.
		 */
		bool contains(const T& item)
		{
			Node* node = m_head.m_next;
			while( node->m_next )
			{
				if( (node->m_item == item) && !node->m_isMarked )
					return true;
				node = node->m_next;
			}
			return false;
		}

		/**
		 * Removes the item pointed to by iter, after removal the Iterator will be pointing to the next item in the list.
		 * The Iterator must be locked and validated before calling this function.
		 */
		void remove(Iterator& iter)
		{
			assert(iter.isValidated());
			Node* newNext = iter.m_curr->m_next;
			iter.m_curr->m_isMarked = true;		//mark as removed, logical removal
			iter.m_pred->m_next = newNext;		//physical removal, atomic writes ensure logical/physical ordering
			iter.m_curr->m_lock.unlock();
			freeNode(iter.m_curr);
			iter.m_curr = newNext;
			iter.m_curr->m_lock.lock();
		}

		/**
		 * Same as remove, but unlocks the iterator after removal. This is more efficient than calling remove followed
		 * by unlock.
		 */
		void removeAndUnlock(Iterator& iter)
		{
			assert(iter.isValidated());
			Node* newNext = iter.m_curr->m_next;
			iter.m_curr->m_isMarked = true;		//mark as removed, logical removal
			iter.m_pred->m_next = newNext;		//physical removal, atomic writes ensure logical/physical ordering
			iter.unlock();
			freeNode(iter.m_curr);
			iter.m_curr = newNext;
		}

		///Removes the first occurrence of item from the list, uses operator== to compare.
		bool remove(const T& item)
		{
			Iterator iter(*this);
			while( iter.hasNext() )
			{
				if( iter.peekNext() == item )
				{
					if( iter.lockAndValidate() )
					{
						removeAndUnlock(iter);
						return true;
					}
					//we failed to validate, we must restart from the beginning to remove this item
					iter.unlock();
					iter.toFront();
				}
				else
				{
					iter.next();
				}
			}
			return false;
		}

		///Removes all occurrences of item from the list, uses operator== to compare.
		void removeAll(const T& item)
		{
			Iterator iter(*this);
			while( iter.hasNext() )
			{
				if( iter.peekNext() == item )
				{
					if( iter.lockAndValidate() )
					{
						removeAndUnlock(iter);
					}
					else
					{
						//we failed to validate, we must restart from the beginning to remove this item
						iter.unlock();
						iter.toFront();
					}
				}
				else
				{
					iter.next();
				}
			}
		}

		bool isEmpty()
		{
			return (m_head.m_next->m_next == NULL);
		}

		///Removes all items from the list, note that this is not fast as it acquires locks on every item.
		void clear()
		{
			Iterator iter(*this);
			while( iter.hasNext() )
			{
				while( true )
				{
					if( iter.lockAndValidate() )
					{
						removeAndUnlock(iter);
						break;
					}
					else
					{
						//validation failed, start again from the beginning of the list
						iter.unlock();
						iter.toFront();
					}
				}
			}
		}

        static_assert(!Allocator::kAbaVulnerable, "Allocator must not be vulnerable to the ABA problem");

	private:
		Node* allocNode()
		{
			Node* node = reinterpret_cast<Node*>(m_alloc.alloc(sizeof(Node)));
			new(node) Node;
			return node;
		}
		void freeNode(Node* node)
		{
			node->~Node();
			m_alloc.free(node);
		}

		struct AllocAndTail : public Allocator
		{
			Node m_tail;
		};
		Node m_head;
		AllocAndTail m_alloc;
	};
}

#endif